#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;

//int n, x, y;
//
//const int N = 1e4 + 10;
//int a[N][4];
//int main()
//{
//	cin >> n;
//	vector<bool> ret(n + 1);
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
//	}
//
//	cin >> x >> y;
//	
//	for (int i = 1; i <= n; i++)
//	{
//		if (x >= a[i][0] && x <= a[i][0] + a[i][2]
//			&& y >= a[i][1] && y <= a[i][1] + a[i][3])
//		{
//			ret[i] = true;
//		}
//	}
//	int j = n;
//	for (; j >= 1; j--)
//	{
//		if (ret[j])
//		{
//			cout << j << endl;
//			break;
//		}
//	}
//	
//	if (!j)
//	{
//		cout << "-1" << endl;
//	}
//	
//	
//	return 0;
//}


//string date1, date2;
//
//int days[13] = { 0,31,29,31,30,31,30,31,31,30,31,30,31 };
//
//
//int main()
//{
//	cin >> date1 >> date2;
//	int begin_year = stoi(date1.substr(0, 4));
//	int end_year = stoi(date2.substr(0, 4));
//	string month_day;
//	int count = 0;
//	for (int i = 1; i <= 12; i++)
//	{
//		for (int j = 1; j <= days[i]; j++)
//		{
//			if (i < 10)
//			{
//				month_day = '0' + to_string(i);
//			}
//			else
//			{
//				month_day = to_string(i);
//			}
//			if (j < 10)
//			{
//				month_day += '0' + to_string(j);
//			}
//			else
//			{
//				month_day += to_string(j);
//			}
//
//			string _year(month_day.rbegin(), month_day.rend());
//			if (stol(date1) <= stol(_year + month_day) && stol(_year+month_day) <= stol(date2))
//			{
//				if (month_day == "0229")
//				{
//					int y = stoi(_year);
//					if (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) && y >= begin_year && y <= end_year)
//					{
//						count++;
//					}
//				}
//
//				else
//				{
//					int y = stoi(_year);
//					if (y >= begin_year && y <= end_year)
//					{
//						count++;
//					}
//				}
//			}
//
//		}
//	}
//
//	cout << count;
//	return 0;
//}

//const int N = 1e5 + 10;
//int n;
//
//int a[N], b[N];
//int main()
//{
//	cin >> n;
//	int _count = 0;
//	int times = 2;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> b[i];
//	}
//	a[1] = 1;
//	while (times)
//	{
//		int i = 2;
//		for (; i <= n+1; i++)
//		{
//			a[i] = b[i - 1] - a[i - 1] - a[i - 2];
//			if (a[i] >= 2 || a[i] < 0)
//			{
//				break;
//			}
//		}
//
//		if (i > n+1 && a[n+1] == 0)
//		{
//			_count++;
//		}
//
//		memset(a, 0, sizeof(a));
//		a[1] = 0;
//		times--;
//	}
//
//	cout << _count;
//
//	return 0;
//}

//class Solution {
//public:
//   static vector<vector<int>> subsets(vector<int>& nums) {
//        int n = nums.size();
//        vector<vector<int>> ret;
//        for (int i = 0; i < (1 << n); i++)
//        {
//            string tmp;
//            int val = i;
//            int k = n + 1;
//            while (k)
//            {
//                int m = val % 2;
//                tmp += to_string(m);
//                val /= 2;
//                k--;
//            }
//            string _plan(tmp.rbegin() + 1, tmp.rend());
//            vector<int> _t;
//            for (int i = 0; i < _plan.size(); i++)
//            {
//                if (_plan[i] == '1')
//                    _t.push_back(nums[i]);
//            }
//            ret.push_back(_t);
//        }
//
//        return ret;
//    }
//};
//
//
//int main()
//{
//    vector<int> nums = { 1,2,3 };
//    vector<vector<int>> ret = Solution::subsets(nums);
//    for (auto& e : ret)
//    {
//        for (auto& x : e)
//        {
//            cout << x << " ";
//        }
//        cout << endl;
//    }
//    return 0;
//}



//int n;
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//
//int main()
//{
//	cin >> n;
//	vector<vector<string>> _input(n, vector<string>(5, string(5, '0')));
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < 5; j++)
//		{
//			cin >> _input[i][j];
//		}
//	}
//	int count = 0;
//	int _min = INT_MAX;
//
//	vector<vector<string>> _tmp = _input;
//
//	int plan[5] = { 0 };
//
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j <= 31; j++)
//		{
//			int val = j;
//			int m = 5;
//			while (m)
//			{
//				int k = val % 2;
//				plan[m - 1] = k;
//				val /= 2;
//				m--;
//			}
//
//			for (int q = 0; q < 5; q++)
//			{
//				if (plan[q])
//				{
//					if (_tmp[i][0][q] == '1')
//					{
//						_tmp[i][0][q] = '0';
//					}
//					else
//					{
//						_tmp[i][0][q] = '1';
//					}
//					count++;
//
//					for (int k = 0; k < 4; k++)
//					{
//						int _row = q + dx[k];
//						int _col = q + dy[k];
//						if (_row >= 0 && _row < 5
//							&& _col >= 0 && _col < 5)
//						{
//							if (_tmp[i][_row][_col] == '1')
//								_tmp[i][_row][_col] = '0';
//							else
//								_tmp[i][_row][_col] = '1';
//
//						}
//					}
//				}
//			}
//			memset(plan, 0, sizeof(plan));
//
//			for (int x = 1; x < 5; x++)
//			{
//				for (int y = 0; y < _tmp[i][x].size(); y++)
//				{
//					if (_tmp[i][x - 1][y] == '0')
//					{
//						if (_tmp[i][x][y] == '1')
//							_tmp[i][x][y] = '0';
//						else
//							_tmp[i][x][y] = '1';
//
//						count++;
//						for (int k = 0; k < 4; k++)
//						{
//							int _row = x + dx[k];
//							int _col = y + dy[k];
//							if (_row >= 0 && _row < 5
//								&& _col >= 0 && _col < 5)
//							{
//								if (_tmp[i][_row][_col] == '1')
//									_tmp[i][_row][_col] = '0';
//								else
//									_tmp[i][_row][_col] = '1';
//
//							}
//						}
//
//					}
//				}
//			}
//
//			_min = min(_min, count);
//			count = 0;
//			_tmp[i] = _input[i];
//		
//
//
//		}
//
//		if (_min <= 6)
//		{
//			cout << _min << endl;
//		}
//		else
//		{
//			cout << "-1" << endl;
//		}
//
//		_min = INT_MAX;
//	
//	}
//
//	return 0;
//}


